A data storage system is typically able to service “data write” or “data read” requests issued by a host computer. A host may be connected to the storage system's external controller or interfaces (IF), through various channels that transfer both data and control information (i.e. control signals). Physical non-volatile media in which data may be permanently or semi-permanently stored include arrays of disk devices, magnetic or optical, which are relatively less expensive than semiconductor based volatile memory (e.g. Random Access Memory) but are relatively much slower in being accessed.
A cache memory is a high-speed buffer located between an IF and the disk device(s), which is meant to reduce the overall latency of Input/Output activity between the storage system and a host accessing data on the storage system. Whenever a host requests data stored in a memory system, the request may be served with significantly lower latency if the requested data is already found in cache, since this data does not have to be brought from the disks. As of the year 2004, speeds of IO transactions involving disk activity are typically on the order of 5-10 milliseconds, whereas IO speeds involving cache (e.g. RAM memory) access are on the order of several nanoseconds.
The relatively high latency associated with disk activity derives from the mechanical nature of the disk devices. In order to retrieve requested data from a disk based device, a disk controller must first cause a disk reading arm to physically move to a track containing the requested data. Once the head of the arm has been placed at the beginning of a track containing the data, the time required to read the accessed data on the relevant track is relatively very short, on the order of several microseconds.
One criterion or parameter which is often used to measure the efficiency of a cache memory system or implementation is a criterion referred to as a hit ratio. A hit ratio of a specific implementation is the percentage of “data read” requests issued by the host that are already found in cache and that consequently did not require time intensive retrieval from disk operations. An ideal cache system would be one reaching a 100% hit ratio. One way known in the art to improve performance by means of enhancing the hit ratio, includes implementing intelligent algorithms that attempt to guess in advance which portions of data stored on a disk device will soon be requested by a host. Once it has been estimated/guessed that some specific data will soon be requested, in anticipation of the request, the algorithm(s) “prefetch” the data into the cache, prior to actually receiving a request for the data.
Prefetch algorithms known in the art commonly fall into one of two categories. The first category or group includes algorithms which are based on the identification of sequential streams of read requests. If the storage system, or the cache management module therein, is able to identify that the host is issuing such sequential streams it may then assume that this kind of activity will be maintained for some time, and accordingly, it will guess which additional portions of data will be requested by the host in the near future. The anticipated portions are thus sent to the cache in advance. U.S. Pat. No. 5,682,500 to Vishlitzky, et al. describes such a prefetch method. The method disclosed by Vishlitzky, et al. involves significant overhead for both triggering the prefetch task and for determining the amount of data to be prefetched as part of each prefetch task.
A second group of prefetch algorithms includes algorithms which are based on the identification of “hot zones” in the storage system. That is, a statistical analysis of activity in the system may indicate that a certain area, defined in advance as a potential “hot zone”, is being intensely addressed by a host, and consequently, a mechanism may be triggered to bring into cache all the data contained in that “hot zone”. The underlying assumption is that such data portions tend to be addressed in their totality, or in their majority, whenever they are addressed over a certain threshold of focused activity.
Unfortunately, in order to increase the cache's hit ratio, the current approaches to prefetch algorithms require a considerable investment in terms of computational resources. In accordance with current prefetch techniques, considerable resources are invested in each of the following tasks: (1) monitoring activity within the storage system (including the cache, disk(s) and possibly also the IFs) on an ongoing basis; (2) determining which data to prefetch; and (3) implementing the desired prefetch policy in a coordinated manner across the system.
There is a need for a method of implementing prefetch operations requiring a relatively small amount of computational and resource overhead while providing for a substantially high cache hit-ratio, and for a device for implementing same. There is a further need for such a method which is based upon a relatively straightforward prefetch criterion in accordance with which variable amounts of data are prefetched depending upon the amount of data meeting the prefetch criterion, and for a device for implementing same. There is yet a further need for such a method which is based upon a substantially flexible prefetch criterion which is configured to accommodate for various cache related statistical deviations.